package algorithm.dynamic;

import util.BaseUtil;

import java.util.Arrays;

/**
 * leetcode : https://leetcode.com/problems/maximum-subarray/description/
 * Difficulty : Easy
 *
 * 经典算法题————最大子数列的和
 * 题目为：
 * 给定一个数列，其中可能有正数也可能有负数
 * 我们的任务是找出连续的一个子数列，使得他们的和最大，求这个最大值，和子数列
 *
 *
 * 解法按从差到优一共四种，时间复杂度依次为：
 *
 *
 * 穷举：O(N^3)
 * 当前节点记录当前的和：O(N^2)，
 * 递归：O(N*logN)
 * 动态规划，递推算法：O(N)   beats 100%
 *
 * 参考文章：https://www.cnblogs.com/conw/p/5896155.html
 * @Author Antony
 * @Since 2018/6/21 14:40
 */
public class MaxSubArray {

    public static void main(String[] args) {
        int k = 10000;
        int[] arr = BaseUtil.randomIntArray(k, 10000, false);
//        int[] arr = new int[]{-2,-8,-1,-5,-9};
//        exhaustion(Arrays.copyOf(arr,k));
        exhaustionOptimize(Arrays.copyOf(arr, k));
        recursion(Arrays.copyOf(arr,k));
        dynamic(Arrays.copyOf(arr,k));
        dynamic_2(Arrays.copyOf(arr,k));
    }

    /**
     * 穷举法
     * 时间复杂度：O(N^3)
     *
     * 两层循环，枚举子列表起点和终点，可以算出最大值
     *
     */
    private static void exhaustion(int[] array){
        long startTime = System.nanoTime();

        int max = array[0];
        int resultBegin = 0;
        int resultEnd = 0;
        for(int begin=0; begin<array.length; begin++){
            for(int end=begin; end<array.length; end++){
                int value = 0;
                for(int i=begin; i<=end; i++){
                    value+=array[i];
                }
                if(value > max){
                    max = value;
                    resultBegin = begin;
                    resultEnd = end;
                }
            }
        }

        long endTime = System.nanoTime();
        System.out.println(String.format("exhaustion --- MAX= %d, 耗时：%s ns", max, (endTime - startTime)));
        System.out.println(String.format("子序列头尾Index为：%d, %d",resultBegin, resultEnd));
    }

    /**
     * 对穷举法的一种优化
     * 时间复杂度：O(N^2)
     *
     * 遍历一遍，然后每一个数组元素赋值为该点之前的和
     * 只要对两个节点取差，就能得到两个节点之间的和
     *
     */
    private static void exhaustionOptimize(int[] array){
        long startTime = System.nanoTime();

        int max = array[0];
        int lowIndex = 0;
        int highIndex = 0;

        int outerPre = 0;
        int innerPre;
        int value;

        // 不需要额外一个循环去计算值，只需要边循环边记录即可
        for(int i=0; i<array.length; i++){
            array[i] = array[i] + outerPre;
            outerPre = array[i];

            innerPre = 0;//初始化
            for(int j=0; j<=i; j++){
                value = array[i] - innerPre;
                if(value > max){
                    max = value;
                    highIndex = i;
                    lowIndex = j;
                }
                innerPre = array[j];
            }
        }
        long endTime = System.nanoTime();
        System.out.println(String.format("exhaustionOptimize --- MAX= %d, 耗时：%s ns", max, (endTime - startTime)));
        System.out.println(String.format("子序列头尾Index为：%d, %d",lowIndex, highIndex));
    }

    /**
     * 递归的解法。
     * 时间复杂度： O(N*logN)
     *
     * 思路：
     * 把数列从中间一分为二。那么最大的值从三个里面选。
     * 1）左边子数列中的最大值
     * 2）右边子数列的最大值
     * 3）从中间开始，向两边相加，的最大值。
     *
     * 注意：
     * 1）在递归中写终止条件，防止无限递归。
     * 2）使用数组中的值声明默认值，不能赋值为0，否则对负值将出错。
     *
     */
    private static void recursion(int[] arr){
        long startTime = System.nanoTime();
        int max = searchCaculate(arr, arr.length/2, 0, arr.length-1);
        long endTime = System.nanoTime();
        System.out.println(String.format("recursion --- MAX= %d, 耗时：%s ns", max, (endTime - startTime)));
    }

    private static int searchCaculate(int[] arr, int base, int leftLimit, int rightLimit){
        // 设置初始值，避免负数时出现错误
        int leftMax = arr[leftLimit];
        int rightMax = arr[rightLimit];
        int max = arr[base];

        if(base-leftLimit <=1 && rightLimit-base <=1){
            max = max > leftMax ? max : leftMax;
            max = max > rightMax ? max : rightMax;
            return max;
        }

        int leftSum = 0;
        for(int i=base; i>=leftLimit; i--){
            leftSum+=arr[i];
            if(leftMax < leftSum){
                leftMax = leftSum;
            }
        }

        int rightSum = 0;
        for(int j=base; j<=rightLimit; j++){
            rightSum +=arr[j];
            if(rightMax < rightSum){
                rightMax = rightSum;
            }
        }

        max = leftMax + rightMax - arr[base];
        int searchLeft = searchCaculate(arr, (leftLimit+base)/2, leftLimit, base-1);
        int searchRight = searchCaculate(arr, (base+rightLimit)/2, base+1, rightLimit);

        max = max > searchLeft ? max : searchLeft;
        max = max > searchRight ? max : searchRight;

        return max;
    }


    /**
     * (leetcode beats 100%)
     * 动态规划
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     *
     * 递推的思想，保存前n个元素的最大和
     *
     * 用 dp[n] 表示以第n个数结尾的最大连续子数列的和。
     * 例如：dp[10]，表示index=10 为最后一个元素的 最大连续子数列的和
     *
     * 那么存在如下递推公式：
     * dp[n] = max(0, dp[n-1]) + arr[n])
     *
     * 那么整个问题的答案就是 max(dp[m]) | m 属于 [1,N]
     *
     * @param arr
     */
    private static void dynamic(int[] arr){
        long startTime = System.nanoTime();

        // 初始化不能为0，而必须是第一个元素。因为可能有负数
        int max = arr[0];
        int dp_n = arr[0];
        for(int i=1; i<arr.length; i++){
            dp_n = arr[i] + (dp_n<0 ? 0 : dp_n);    //dp_n 是以n个索引结尾的最大债，所以必然要加arr[n] 然后判断上一个结尾的最大值是否大于0，大于0则加，否则不加
            max = max > dp_n ? max : dp_n;
        }

        long endTime = System.nanoTime();
        System.out.println(String.format("dynamic --- MAX= %d, 耗时：%s ns", max, (endTime - startTime)));
    }


    /**
     * 另一个动态规划
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     *
     * 思路：维护最小和
     *
     * 对第二个算法的优化，在第二个算法中，数组中的每一个元素表示该元素之前所有元素的和。
     * 也就是说array[i] = sum(array[0] + ... array[i])
     *
     * 那么在以第 i 个元素结尾的子序列中，最大的值为 sum[i] - min(sum[0] ... sum[i-1])
     * 也就是说，在遍历的时维护一个 i 之前的最小和
     * 那么 max[i] = sun[i] - min(sum[0]...sum[i-1])
     *
     * @param array
     */
    private static void dynamic_2(int[] array){
        long startTime = System.nanoTime();

        int max = array[0];
        int left_min = array[0];
        int temp;
        for(int i=1; i<array.length; i++){
            array[i] += array[i-1]; //计算前序列和

            temp = array[i] - left_min;
            max = max > temp ? max : temp;
            left_min = left_min < array[i] ? left_min : array[i];
        }

        long endTime = System.nanoTime();
        System.out.println(String.format("dynamic_2 --- MAX= %d, 耗时：%s ns", max, (endTime - startTime)));
    }

}
